package com.neusoft.recursion.eightQueen;

import lombok.Data;

/**
 * @Author lichunlong lcl253137@alibaba-inc.com
 * @Desc 八皇后问题
 * @Date 2024-11-02
 */
@Data
public class Queen8 {

    /**
     * 表示共有多少个皇后
     */
    int max = 8;

    /**
     * 保存皇后放置位置的结果: 比如arr = {0, 4, 7, 5, 2, 6, 1, 3}
     */
    int[] queenArray = new int[max];

    private int count = 0;

    private int judgeCount = 0;

    /**
     * 放置第n个皇后: check方法是每一次递归时, 进入到check中都有for(int i = 0; i < max; i++)，因此会有回溯
     *
     * @param index 第N个皇后
     */
    public void check(int index) {
        if (index == max) {
            // 8个皇后已全部放好
            printQueue();
            return;
        }

        // 依次放入皇后，并判断是否冲突
        for (int i = 0; i < max; i++) {
            // 先把当前的皇后放到该行的第1列
            queenArray[index] = i;
            // 判断当放置第N个皇后到i列时，是否冲突
            if (judge(index)) {
                // 不冲突就接着放n+1个皇后【即开始递归】
                check(index + 1);
            }
        }
    }

    /**
     * 当我们放置第N个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突
     *
     * @param index 第N个皇后
     * @return 是否冲突的标识
     */
    public boolean judge(int index) {
        judgeCount++;
        for (int i = 0; i < index; i++) {
            // 1、array[i] == array[n]: 判断第N个皇后是否和前面的N-1个皇后是否在同一列
            // 2、Math.abs(n-i) == Math.abs(array[n] - array[i]): 判断第N个皇后是否和第i皇后是否在同一斜线【横坐标减横坐标等于纵坐标减纵坐标】
            // 3、判断是否在同一行, 没有必要【N每次都在递增】
            if (queenArray[i] == queenArray[index] || Math.abs(index - i) == Math.abs(queenArray[index] - queenArray[i])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 输出皇后摆放的位置
     */
    private void printQueue() {
        count++;
        for (int queueIndex : queenArray) {
            System.out.print(queueIndex + " ");
        }
        System.out.println();
    }
}
